package violentRecursion;

import java.util.List;

/**
 * @author kunkun
 * @className LeetCode_139
 * @Description 单词拆分
 * @date 2025/3/13 17:50
 */
public class LeetCode_139 {
    public boolean wordBreak(String s, List<String> wordDict) {
//        return solution_1(s,wordDict,0);
        return solution_2(s,wordDict);
    }

    //暴力递归
    private boolean solution_1(String s, List<String> wordDict,int index) {
        //1. 判断
        if (index>=s.length()){
            return true;
        }
        //2. 递归体
        for (int i=0;i<wordDict.size();i++) {
            //2.1 定义结果
            Boolean flag = false;
            String word = wordDict.get(i);
            //2.2 判断开头
            if (s.substring(index).startsWith(word)){
                flag = solution_1(s,wordDict,index+word.length());
            }
            //2.3 返回结果
            if (flag){
                return true;
            }
        }
        return false;
    }

    //动态规划
    private boolean solution_2(String s, List<String> wordDict) {
        //1. 定义返回数组
        Boolean[] res = new Boolean[s.length()];
        for (int i = 0; i < res.length; i++) {
            res[i]=false;
        }

        //2. 循环
        for (int i = res.length-1; i >=0; i--) {
            //2.1 逐单词判断
            for (String word : wordDict) {
                Boolean flag = false;
                //2.2 判断开头
                if (s.substring(i).startsWith(word)){
                    flag = (i+word.length()<=res.length-1)?res[i+word.length()]:true;
                }
                //2.3 返回结果
                if (flag){
                    res[i]= true;
                    break;
                }
            }
        }



        return res[0];
    }

}
